package basis.netease.easy;

import java.util.Scanner;
import java.util.Stack;

/**
 * 7-28 去除重复字母
 * 给你一个字符串 s ，请你去除字符串中重复的字符，使得每个字符只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 * 输入格式:
 * 输入一个字符串，字符串的长度小于1000。字符内容是ASCII码，ASCII码定义了128个字符，包括控制字符（例如换行符、制表符、退格等）和可显示的字符（包括数字、字母、标点符号和一些特殊字符）。
 * 输出格式:
 * 输出处理后的字符串
 * 输入样例:
 * 在这里给出一组输入。例如：
 * abecbcd
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * abecd
 */
public class Main_21 {

    public static String removeDuplicateLetters(String s) {
        int[] count = new int[128]; // 统计字符之后还会出现的次数
        boolean[] visited = new boolean[128]; // 标记字符是否已在栈中
        Stack<Character> stack = new Stack<>(); // 最终返回的字符串
        for (char c : s.toCharArray()) {
            count[c]++;
        }
        for (char c : s.toCharArray()) {
            count[c]--;
            // 如果字符已经在栈中，跳过
            if (visited[c]) {
                continue;
            }
            // 移除栈顶元素，直到找到一个小于当前字符或者后面不会再出现的字符
            while (!stack.isEmpty() && c < stack.peek() && count[stack.peek()] > 0) {
                visited[stack.pop()] = false;
            }
            stack.push(c);
            visited[c] = true;
        }
        StringBuilder result = new StringBuilder();
        for (Character c : stack) {
            result.append(c);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        System.out.println(removeDuplicateLetters(input));
    }

}
